///**
// *
// */
//package niuke.wap;
//
//import java.util.HashSet;
//import java.util.Scanner;
//
///**
// * @author zhongfang
// *
// */
//public class test1 {
//
//	static int minStep = Integer.MAX_VALUE;
//	static HashSet<String> visited = new HashSet<>();
//
//	public static void BFS(int i, int j, int countC[][], int countR[][], int step, int target) {
//		if (visited.contains(i + "" + j)) {
//			return;
//		}
//		String string = "";
//		string.startsWith(prefix);
//		visited.add(i + "" + j);
//		// 判断棋盘剩余棋子是否是j，如果小于，则返回
//		int count = 0;
//		int n = countC.length;
//		int m = countC[0].length;
//		int startR = 0, endR = 0;
//		int startC = 0, endC = 0;
//		if (i >= 0) {
//			startR = 0;
//			endR = n - i;
//		} else {
//			startR = -i - 1;
//			endR = n - 1;
//		}
//		if (j >= 0) {
//			startC = 0;
//			endC = m - j;
//		} else {
//			startC = -j - 1;
//			endC = m - 1;
//		}
//		// for (int k = startR; k < endR; k++) {
//		// for (int k2 = startC; k2 < endC; k2++) {
//		// if (matrix[k][k2])
//		// count++;
//		// }
//		// }
//		if (count == target) {
//			minStep = Math.min(minStep, step);
//		} else if (count < target) {
//			return;
//		}
//
//		// 当前值向上下左右走
//		// 右，去除的个数
//		int nextTarget = target;
//		// 从i到n-1的一列
//		if (i <= 0 && j <= 0) {
//			nextTarget -= countC[n - 1][j] - countC[i][j];
//		} else if (i <= 0 && j >= 0) {
//
//		} else if (i >= 0 && j <= 0) {
//
//		} else {
//
//		}
//
//		// BFS(i + 1, j, matrix, step + 1, target);
//		// BFS(i, j + 1, matrix, step + 1, target);
//		// BFS(i - 1, j, matrix, step + 1, target);
//		// BFS(i, j - 1, matrix, step + 1, target);
//	}
//
//	/**
//	 * @param args
//	 */
//	public static void main(String[] args) {
//		Scanner scanner = new Scanner(System.in);
//		int n = scanner.nextInt();
//		int m = scanner.nextInt();
//		scanner.nextLine();
//		boolean[][] matrix = new boolean[n][m];
//		int totalCount = 0;
//		for (int i = 0; i < n; i++) {
//			String string = scanner.nextLine();
//			for (int j = 0; j < string.length(); j++) {
//				if (string.charAt(j) == 'o') {
//					matrix[i][j] = true;
//					totalCount++;
//				}
//			}
//		}
//		int k = scanner.nextInt();
//		if (totalCount < k) {
//			System.out.println(-1);
//			return;
//		}
//		int[][] countCol = new int[n][m];
//		for (int i = 0; i < n; i++) {
//			int c = 0;
//			for (int j = 0; j < m; j++) {
//				if (matrix[i][j]) {
//					c++;
//				}
//				countCol[i][j] = c;
//			}
//		}
//
//		int[][] countRow = new int[n][m];
//		for (int i = 0; i < m; i++) {
//			int c = 0;
//			for (int j = 0; j < n; j++) {
//				if (matrix[j][i]) {
//					c++;
//				}
//				countRow[j][i] = c;
//			}
//		}
//		BFS(0, 0, countCol, countRow, 0, k);
//		if (minStep != Integer.MAX_VALUE) {
//			System.out.println(minStep - 1);
//		} else {
//			System.out.println(-1);
//		}
//		//
//		// int[][][] dp = new int[2 * n + 1][2 * m + 1][k + 1];
//		// for (int i = 0; i < dp.length; i++) {
//		// for (int j = 0; j < dp[0].length; j++) {
//		// for (int j2 = 0; j2 < dp[0][0].length; j2++) {
//		// dp[i][j][j2] = Integer.MAX_VALUE;
//		// }
//		// }
//		// }
//		// dp[n][m][0] = 0;
//		// for (int i = 0; i < n; i++) {// 向右移动
//		// for (int j = 0; j < n; j++) {
//		// for (int j2 = 0; j2 <k+1; j2++) {
//		// if (j != 0) {
//		// //数第j列
//		// int c=
//		// dp[i][j][k] = Math.min(dp[i][j][j2], dp[i][j-1][j2-]);
//		// }
//		// }
//		// }
//		// }
//	}
//}
